/* Program: Naive-bi.c
 * Author: Patanamon Thongtanunam(pamon)
 * Describe: This is program for calculate PageRank by the Power Method 
 * from standford webgraph in binary file
 * */
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>

#define SIZE 8618351
#define c 0.85
#define treshole 0.00001
void init_dest(float dest[])
{
	int i;
	for(i=0 ; i < SIZE;i++)
		dest[i] = 0;
}
main()
{
	FILE* fp;
	int src,dest,cnt;
	int index_src = 0,index_dest=1,i,round = 0;
	char *not_dangling;
	float **score,dangling,residual,sum;
	
	time_t start = clock();
	
	score = (float**)malloc(sizeof(float*) *2);
	score[0] = (float*)malloc(sizeof(float) * SIZE);
	score[1] = (float*)malloc(sizeof(float) * SIZE);
	not_dangling = (char*)malloc(sizeof(char) * SIZE);
	

	for(i=0;i<SIZE;i++)
		score[index_src][i] = 1.0/(float)SIZE;

	sum = 0;
	for(i=0;i<SIZE;i++)
		sum += score[index_src][i];

//	printf("sum = %E\n",sum);

	residual = 1;
	while(residual > treshole)
	{
		round += 1;
		if((fp = fopen("wbCt100Sep08/webgraph.bin","r")) == NULL)
		{
			printf("FILE NOT FOUND\n");
			return 0;
		}

		init_dest(score[index_dest]);
	
		while(fread(&src,sizeof(int),1,fp) != 0)
		{
			not_dangling[src] = 1;
			
			fread(&cnt,sizeof(int),1,fp);
	
			for(i=0;i<cnt;i++)
			{
				fread(&dest,sizeof(int),1,fp);
				score[index_dest][dest] += score[index_src][src]/(float)cnt;
			}
		}
		fclose(fp);
		
		dangling=0.0;
		for(i=0;i<SIZE;i++)
			if(!not_dangling[i])
				dangling += score[index_src][i]/(float)SIZE;

		residual = 0;
	//	sum = 0;
		for(i = 0;i<SIZE;i++)
		{
			score[index_dest][i] += dangling;
			score[index_dest][i] = score[index_dest][i]*c + (1.0-c)/(float)SIZE;
	//		sum += score[index_dest][i];
			residual += fabs(score[index_src][i] - score[index_dest][i]);
		
		}
		index_dest = (index_dest+1)%2;
		index_src = (index_src +1)%2;

		printf("residual >> %E  \n",residual);
//		printf("SUM = %E\n",sum);
	}

		time_t stop = clock();
		printf("%.10lf\n",(float)(stop - start)/CLOCKS_PER_SEC);
		for(i=0;i<SIZE;i++)
			sum += score[index_src][i];
		printf("SUM = %E\n",sum);
		printf("number of iteration %d \n",round);
	//	for(i=0;i<SIZE;i++)
	//		printf("%d:%.20lf\n",i,score[index_src][i]);
}
